{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Toss Strange Coins"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming #probability-and-statistics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划 #概率与统计"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: probabilityOfHeads"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #抛掷硬币"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一些不规则的硬币。在这些硬币中，<code>prob[i]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;枚硬币正面朝上的概率。</p>\n",
    "\n",
    "<p>请对每一枚硬币抛掷&nbsp;<strong>一次</strong>，然后返回正面朝上的硬币数等于&nbsp;<code>target</code>&nbsp;的概率。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>prob = [0.4], target = 1\n",
    "<strong>输出：</strong>0.40000\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>prob = [0.5,0.5,0.5,0.5,0.5], target = 0\n",
    "<strong>输出：</strong>0.03125\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= prob.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= prob[i] &lt;= 1</code></li>\n",
    "\t<li><code>0 &lt;= target&nbsp;</code><code>&lt;= prob.length</code></li>\n",
    "\t<li>如果答案与标准答案的误差在&nbsp;<code>10^-5</code>&nbsp;内，则被视为正确答案。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [toss-strange-coins](https://leetcode.cn/problems/toss-strange-coins/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [toss-strange-coins](https://leetcode.cn/problems/toss-strange-coins/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0.4]\\n1', '[0.5,0.5,0.5,0.5,0.5]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        dp = [1.0] + [0.0] * target\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(min(i, target), 0, -1):\n",
    "                dp[j] = dp[j-1] * prob[i-1] + dp[j] * (1-prob[i-1])\n",
    "            dp[0] *= (1-prob[i-1])\n",
    "        \n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        res = [0.0] * target + [1.0]\n",
    "        for p in prob:\n",
    "            for i in range(target):\n",
    "                res[i] = res[i] * (1 - p) + res[i+1] * p\n",
    "            res[-1] *= (1-p)\n",
    "        return res[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        dp = [0 for _ in range(target + 1)]\n",
    "        dp[0] = 1- prob[0]\n",
    "        if target >= 1:\n",
    "            dp[1] = prob[0]\n",
    "        for i in range(1,n):\n",
    "            for j in range(target,-1,-1):\n",
    "                dp[j] = dp[j] * (1-prob[i]) + (\n",
    "                    dp[j-1] * prob[i] if j - 1>= 0 else 0\n",
    "                )\n",
    "        \n",
    "        return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(n):\n",
    "          for j in range(min(i+1, target), -1, -1):\n",
    "            dp[j] *= (1 - prob[i])\n",
    "            if j > 0:\n",
    "              dp[j] += dp[j-1] * prob[i]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        dp = [0.0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i, p in enumerate(prob):\n",
    "            for j in range(min(i + 1, target), 0, -1):\n",
    "                dp[j] = dp[j] * (1 - p) + dp[j - 1] * p\n",
    "            dp[0] *= (1 - p)\n",
    "        return dp[target]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(n):\n",
    "          for j in range(min(i+1, target), -1, -1):\n",
    "            dp[j] *= (1 - prob[i])\n",
    "            if j > 0:\n",
    "              dp[j] += dp[j-1] * prob[i]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        dp = [0] * (target + 2)\n",
    "        n = len(prob)\n",
    "        dp[0] = 1 - prob[0]\n",
    "        dp[1] =prob[0]\n",
    "        # print(dp)\n",
    "        for i in range(1,n):\n",
    "            if prob[i]==0:\n",
    "                continue\n",
    "            ndp = [0] * (target + 2)\n",
    "            ndp[0]=dp[0]*(1-prob[i])\n",
    "            for t in range(1, target + 2):\n",
    "                ndp[t] = dp[t - 1] * prob[i]+dp[t]*(1-prob[i])\n",
    "            dp=ndp\n",
    "            # print(dp)\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i < 0:\n",
    "        #         return +(j == 0)\n",
    "        #     ans = (1 - prob[i])*dfs(i - 1,j)\n",
    "        #     if j > 0:\n",
    "        #         ans += prob[i]*dfs(i - 1,j - 1) \n",
    "        #     return ans\n",
    "        # return dfs(n - 1,target)\n",
    "\n",
    "        # f = [[0]*(target + 1) for _ in range(n + 1)]\n",
    "        # f[0][0] = 1\n",
    "\n",
    "        # for i,x in enumerate(prob):\n",
    "        #     for j in range(target + 1):\n",
    "        #         f[i + 1][j] = f[i][j]*(1 - x)\n",
    "        #         if j > 0:\n",
    "        #             f[i + 1][j] += f[i][j - 1] * x\n",
    "        # return f[-1][-1]\n",
    "\n",
    "        f = [0]*(target + 1)\n",
    "        f[0] = 1\n",
    "\n",
    "        for i,x in enumerate(prob):\n",
    "            for j in range(target,-1,-1):\n",
    "                f[j] = f[j]*(1 - x)\n",
    "                if j > 0:\n",
    "                    f[j] += f[j - 1] * x\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        coin_list = [1] + [0] * (target + 1)\n",
    "        for i in range(len(prob)):\n",
    "            for j in range(min(i, target), -1, -1):\n",
    "                temp = coin_list[j] * prob[i]\n",
    "                coin_list[j+1] += temp\n",
    "                coin_list[j] -= temp\n",
    "        \n",
    "        return coin_list[target]\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(target, 0, -1):\n",
    "                dp[j] = dp[j - 1] * prob[i - 1] + dp[j] * (1 - prob[i - 1])\n",
    "            dp[0] = dp[0] * (1 - prob[i - 1])\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n=len(prob)\n",
    "        dp=[0]*(target+1)\n",
    "        pro=1\n",
    "        for x in prob:\n",
    "            pro=pro*(1-x)\n",
    "        #dp[0]=pro\n",
    "        dp[0]=1\n",
    "        for i,p in enumerate(prob):\n",
    "            for j in range(target,-1,-1):\n",
    "                dp[j]=dp[j]*(1-p)\n",
    "                if j>=1:\n",
    "                    dp[j]+=dp[j-1]*p\n",
    "                \n",
    "        return dp[target]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        # dp[i][j]表示前i硬币有j个正面朝上的概率，求dp[n][target]\n",
    "        # dp[i][j] = dp[i-1][j-1]*prob[i] + dp[i-1][j]*(1-prob[i])\n",
    "        # dp[1][1] = prob[i], dp[1][0] = 1-prob[i]\n",
    "        n = len(prob)\n",
    "        dp = [0]*(n+1)\n",
    "        dp[0] = 1\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(i, -1, -1):\n",
    "                if j == 0:\n",
    "                    dp[j] = dp[j] * (1-prob[i-1])\n",
    "                else:\n",
    "                    dp[j] = dp[j-1] * prob[i-1] + dp[j] * (1-prob[i-1])\n",
    "\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        N = len(prob)\n",
    "        if N==1:\n",
    "            if target==1:\n",
    "                return prob[0]\n",
    "            else:\n",
    "                return prob[1]\n",
    "        dp = [0]*(N+1)\n",
    "        dp[0] = 1-prob[0]\n",
    "        dp[1] = prob[0]\n",
    "\n",
    "        for i in range(1,N):\n",
    "            print(i)\n",
    "            temp_dp = [0]*(N+1)\n",
    "            for j in range(0,i+2):\n",
    "                if j == 0:\n",
    "                    temp_dp[j] = dp[j]*(1-prob[i])\n",
    "                if j==i+1:\n",
    "                    temp_dp[j] = dp[j-1]*(prob[i])\n",
    "                else:\n",
    "                    # print(j)\n",
    "                    temp_dp[j] = dp[j]*(1-prob[i])+dp[j-1]*(prob[i])\n",
    "            dp = temp_dp\n",
    "\n",
    "        \n",
    "        return temp_dp[target]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        if target>n:\n",
    "            return 0 \n",
    "        \n",
    "        dp = [[0] * (target+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            dp[i][0] = dp[i-1][0] * (1-prob[i-1]) \n",
    "            for j in range(1, target+1):\n",
    "                if j>i:\n",
    "                    break \n",
    "                dp[i][j] = dp[i-1][j-1] * prob[i-1] + dp[i-1][j] * (1-prob[i-1])\n",
    "        \n",
    "        return dp[-1][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        dp  = [[0] * (target + 1) for _ in range(n + 1)]\n",
    "\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n+1):\n",
    "            dp[i][0] = dp[i-1][0] * (1-prob[i-1])\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for k in range(1, min(i, target)+1):\n",
    "                dp[i][k] = dp[i-1][k] * (1-prob[i-1]) + dp[i-1][k-1] * prob[i-1]\n",
    "\n",
    "        return dp[n][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob, target):\n",
    "        n = len(prob)\n",
    "        dp = [[0] * (target + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(min(i, target) + 1):\n",
    "                dp[i][j] = dp[i - 1][j] * (1 - prob[i - 1])\n",
    "                if j > 0:\n",
    "                    dp[i][j] += dp[i - 1][j - 1] * prob[i - 1]\n",
    "        return dp[-1][min(n, target)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        # dp[i][j] 是前i枚硬币，有j个正面朝上的概率\n",
    "        # dp[i][j] = dp[i-1][j] * (1 - p[i]) + dp[i-1][j-1] * p[i]\n",
    "        n = len(prob)\n",
    "        dp = [[0] * (target+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        \n",
    "        for i, p in enumerate(prob, 1):\n",
    "            dp[i][0] = dp[i-1][0] * (1-p)\n",
    "            for j in range(1, min(i, target) + 1):\n",
    "                dp[i][j] = dp[i-1][j] * (1-p) + dp[i-1][j-1] * p\n",
    "\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        # dp[i][j]表示0-i-1的硬币，正面朝上的硬币数等于target的概率为dp[i][j]\n",
    "        dp = [[0] * (target + 1) for _ in range(n + 1)]\n",
    "        # dp初始化\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1])\n",
    "        # 动态规划\n",
    "        for i in range(1, n + 1):\n",
    "            for k in range(1, min(i, target) + 1):\n",
    "                dp[i][k] = dp[i - 1][k] * (1 - prob[i - 1]) + dp[i - 1][k - 1] * prob[i - 1]\n",
    "        return dp[n][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        # dp[i][j] 是前i枚硬币，有j个正面朝上的概率\n",
    "        # dp[i][j] = dp[i-1][j] * (1 - p[i]) + dp[i-1][j-1] * p[i]\n",
    "        n = len(prob)\n",
    "        dp = [[0] * (target+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i, p in enumerate(prob, 1):\n",
    "            dp[i][0] = dp[i-1][0] * (1-p)\n",
    "            for j in range(1, min(i, target) + 1):\n",
    "                dp[i][j] = dp[i-1][j] * (1-p) + dp[i-1][j-1] * p\n",
    "\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        N = len(prob)\n",
    "        dp = [[0] * (target+1) for _ in range(N)]\n",
    "        dp[0][0] = (1-prob[0])\n",
    "\n",
    "        for i in range(1, N):\n",
    "            dp[i][0] = dp[i-1][0] * (1-prob[i])\n",
    "        \n",
    "        for i in range(N):\n",
    "            for j in range(1, target+1):\n",
    "                if j > i+1:\n",
    "                    break\n",
    "                if i == 0 and j == 1:\n",
    "                    dp[i][j] = prob[0]\n",
    "                    continue\n",
    "                dp[i][j] = dp[i-1][j-1]*prob[i] + dp[i-1][j]*(1-prob[i])\n",
    "        \n",
    "        return dp[N-1][target] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "    \n",
    "        # Initialize a 2D list dp to store the probability values\n",
    "        dp = [[0.0] * (target + 1) for _ in range(n + 1)]\n",
    "        \n",
    "        # Initialize the base case: With 0 coins, the probability of 0 heads is 1.\n",
    "        dp[0][0] = 1.0\n",
    "        \n",
    "        # Initialize probabilities for the case where the first i coins all have tails facing up.\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1])\n",
    "        \n",
    "        # Calculate probabilities for other cases.\n",
    "        for i in range(1, n + 1):\n",
    "            for k in range(1, min(i, target) + 1):\n",
    "                dp[i][k] = dp[i - 1][k] * (1 - prob[i - 1]) + dp[i - 1][k - 1] * prob[i - 1]\n",
    "        \n",
    "        # Return the probability of getting the desired number of heads.\n",
    "        return dp[n][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        N = len(prob)\n",
    "        dp = [[0 for _ in range(target+1)] for _ in range(N+1)]\n",
    "        dp[0][0] = 1.0\n",
    "\n",
    "        for i in range(1, N+1):\n",
    "            dp[i][0] = (dp[i-1][0] * (1 - prob[i-1]))\n",
    "            for j in range(1, min(i+1, target+1)):\n",
    "                dp[i][j] = prob[i-1] * dp[i-1][j-1] + (1 - prob[i-1]) * dp[i-1][j] \n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        N = len(prob)\n",
    "        dp = [[0 for _ in range(target+1)] for _ in range(N+1)]\n",
    "        dp[0][0] = 1.0\n",
    "\n",
    "\n",
    "        for i in range(1, N+1):\n",
    "            dp[i][0] = (dp[i-1][0] * (1 - prob[i-1]))\n",
    "            for j in range(1, target+1):\n",
    "                if j > i:\n",
    "                    dp[i][j] = 0.0\n",
    "                else:\n",
    "                    dp[i][j] = prob[i-1] * dp[i-1][j-1] + (1 - prob[i-1]) * dp[i-1][j] \n",
    "        #print(dp)\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        dp[1][0] = 1-prob[0]\n",
    "        dp[1][1] = prob[0]\n",
    "        for i in range(2,n+1):\n",
    "            dp[i][0] = dp[i-1][0]*(1-prob[i-1])\n",
    "\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(1,i+1):\n",
    "                dp[i][j] = prob[i-1]*dp[i-1][j-1] + (1-prob[i-1])*dp[i-1][j]\n",
    "\n",
    "        return dp[n][target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        # dp[i][j]表示前i硬币有j个正面朝上的概率，求dp[n][target]\n",
    "        # dp[i][j] = dp[i-1][j-1]*prob[i] + dp[i-1][j]*(1-prob[i])\n",
    "        # dp[1][1] = prob[i], dp[1][0] = 1-prob[i]\n",
    "        n = len(prob)\n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        # dp[1][0], dp[1][1] = 1-prob[0], prob[0]\n",
    "        dp[0][0] = 1\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(i+1):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] * (1-prob[i-1])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j-1] * prob[i-1] + dp[i-1][j] * (1-prob[i-1])\n",
    "\n",
    "        return dp[n][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n=len(prob)\n",
    "        dp=[[0]*(n+1) for _ in range(n+1)]\n",
    "        # if target==0:\n",
    "        #     ans=(1-prob[0])\n",
    "        #     for num in prob[1:]:\n",
    "        #         ans*=(1-num)\n",
    "        #     return ans\n",
    "        dp[0][0],dp[0][1]=1,0\n",
    "        for i in range(1,n+1):\n",
    "            dp[i][0]=dp[i-1][0]*(1-prob[i-1])\n",
    "        for i in range(1,target+1):\n",
    "            dp[i][i]=dp[i-1][i-1]*prob[i-1]\n",
    "            for j in range(i+1,n+1):\n",
    "                dp[j][i]=prob[j-1]*dp[j-1][i-1]+(1-prob[j-1])*dp[j-1][i]\n",
    "        # for j in range(target+1,n+1):\n",
    "        #     dp[j][target]=prob[j-1]*dp[j-1][target-1]+(1-prob[j-1])*dp[j-1][target]\n",
    "            # for j in range(i+1,n+1):\n",
    "            #     dp[j][i]=prob[j-1]*dp[j-1][i-1]+(1-prob[j-1])*dp[j-1][i]\n",
    "        return dp[n][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        # dp[i][j]表示前i硬币有j个正面朝上的概率，求dp[n][target]\n",
    "        # dp[i][j] = dp[i-1][j-1]*prob[i] + dp[i-1][j]*(1-prob[i])\n",
    "        # dp[1][1] = prob[i], dp[1][0] = 1-prob[i]\n",
    "        n = len(prob)\n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        # dp[1][0], dp[1][1] = 1-prob[0], prob[0]\n",
    "        dp[0][0] = 1\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(i+1):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] * (1-prob[i-1])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j-1] * prob[i-1] + dp[i-1][j] * (1-prob[i-1])\n",
    "\n",
    "        return dp[n][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        dp = [[0.0] * (target + 1) for _ in range(n)]\n",
    "        dp[0][0] = 1 - prob[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][0] * (1 - prob[i])\n",
    "        for j in range(1, target + 1):\n",
    "            if j == 1:\n",
    "                dp[0][j] = prob[0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, target + 1):\n",
    "                dp[i][j] = dp[i-1][j] * (1-prob[i]) + dp[i-1][j-1] * (prob[i])\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n",
    "        # n = len(prob)\n",
    "        # dp = [[0.0] * (target + 1) for _ in range(n)]\n",
    "        # dp[0][0] = 1 - prob[0]\n",
    "        # if target>0:\n",
    "        #     dp[0][1] = prob[0]\n",
    "        # for i in range(1, n):\n",
    "        #     dp[i][0] = dp[i-1][0] * (1- prob[i])\n",
    "        #     for j in range(1, target + 1):\n",
    "        #         dp[i][j] = dp[i-1][j] * (1 - prob[i]) + dp[i-1][j-1] * prob[i]\n",
    "        # return dp[n-1][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        k = target+1\n",
    "        n = len(prob)\n",
    "        dp = [[0] * k for _ in range(n)]\n",
    "        dp[0][0] = (1-prob[0])\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][0] * (1-prob[i])\n",
    "        if k == 1:\n",
    "            return dp[-1][0]\n",
    "        dp[0][1] = prob[0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, k):\n",
    "                dp[i][j] = dp[i-1][j] * (1-prob[i]) + dp[i-1][j-1] * prob[i]\n",
    "\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i < 0:\n",
    "        #         return +(j == 0)\n",
    "        #     ans = (1 - prob[i])*dfs(i - 1,j)\n",
    "        #     if j > 0:\n",
    "        #         ans += prob[i]*dfs(i - 1,j - 1) \n",
    "        #     return ans\n",
    "        # return dfs(n - 1,target)\n",
    "\n",
    "        f = [[0]*(target + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 1\n",
    "\n",
    "        for i,x in enumerate(prob):\n",
    "            for j in range(target + 1):\n",
    "                f[i + 1][j] = f[i][j]*(1 - x)\n",
    "                if j > 0:\n",
    "                    f[i + 1][j] += f[i][j - 1] * x\n",
    "        return f[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i < 0:\n",
    "        #         return +(j == 0)\n",
    "        #     ans = (1 - prob[i])*dfs(i - 1,j)\n",
    "        #     if j > 0:\n",
    "        #         ans += prob[i]*dfs(i - 1,j - 1) \n",
    "        #     return ans\n",
    "        # return dfs(n - 1,target)\n",
    "\n",
    "        f = [[0]*(target + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 1\n",
    "\n",
    "        for i,x in enumerate(prob):\n",
    "            for j in range(target + 1):\n",
    "                f[i + 1][j] = f[i][j]*(1 - x)\n",
    "                if j > 0:\n",
    "                    f[i + 1][j] += f[i][j - 1] * x\n",
    "        return f[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        dp = [[0] * (target + 1) for _ in range(n)]\n",
    "        dp[0][0] = 1.0 - prob[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][0] * (1 - prob[i])\n",
    "\n",
    "        for j in range(1, target + 1):\n",
    "            if j == 1:\n",
    "                dp[0][j] = prob[0]\n",
    "            else:\n",
    "                dp[0][j] = 0\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, target + 1):\n",
    "                dp[i][j] = dp[i-1][j] * (1 - prob[i]) + dp[i-1][j-1] * prob[i]\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # n = len(prob)\n",
    "        # dp = [[0.0] * (target + 1) for _ in range(n)]\n",
    "        # dp[0][0] = 1 - prob[0]\n",
    "        # if target>0:\n",
    "        #     dp[0][1] = prob[0]\n",
    "        # for i in range(1, n):\n",
    "        #     dp[i][0] = dp[i-1][0] * (1- prob[i])\n",
    "        #     for j in range(1, target + 1):\n",
    "        #         dp[i][j] = dp[i-1][j] * (1 - prob[i]) + dp[i-1][j-1] * prob[i]\n",
    "        # return dp[n-1][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        m,n=len(prob),target\n",
    "        dp=[[0]*(n+1) for i in range(m+1)]\n",
    "        dp[0][0]=1\n",
    "        for i in range(m):\n",
    "            dp[i+1][0]=dp[i][0]*(1-prob[i])\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                dp[i][j]=dp[i-1][j-1]*prob[i-1]+dp[i-1][j]*(1-prob[i-1])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        num = len(prob)\n",
    "        dp = [[0] * (target + 1) for _ in range(num + 1)]\n",
    "        dp[0][0] = 1\n",
    "\n",
    "        for i in range(1, num + 1):\n",
    "            dp[i][0] = (1 - prob[i - 1]) * dp[i - 1][0]\n",
    "\n",
    "        for i in range(1, num + 1):\n",
    "            for j in range(1, target + 1):\n",
    "                dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1])\n",
    "\n",
    "        return dp[num][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        if n==1:\n",
    "            return prob[0]\n",
    "        \n",
    "        # dp[i][j]：前i枚硬币正面朝上数量为j的概率\n",
    "        dp = [[0] * (target+1) for _ in range(n+1)]\n",
    "        \n",
    "        dp[0][0] = 1\n",
    "\n",
    "        for i in range(1,n+1): # 填充第一列\n",
    "        # 前i枚硬币正面朝上数量为0的概率等于前i-1枚硬币正面朝上数量为0的概率*第i枚反面朝上的概率\n",
    "            dp[i][0] = dp[i-1][0] * (1-prob[i-1])\n",
    "        \n",
    "        # 开始动态规划\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,target+1):\n",
    "                # 前i枚硬币正面朝上数量为j的概率等于\n",
    "                #  前i-1枚硬币正面朝上数量为j的概率*第i枚反面朝上的概率\n",
    "                # 加上\n",
    "                # 前i-1枚硬币正面朝上数量为j-1的概率*第i枚正面面朝上的概率 \n",
    "                dp[i][j] = dp[i-1][j] * (1-prob[i-1])  + dp[i-1][j-1] * prob[i-1]\n",
    "        return dp[n][target]\n",
    "        # return dp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        # dp[i][j] = dp[i-1][j-1] * pro[i] + dp[i-1][j] * (1-pro[i])\n",
    "        n = len(prob)\n",
    "        dp = [[0.0]*(target+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        # i = 1..n,  j = 0\n",
    "        for i in range(1,n+1):\n",
    "            dp[i][0] = dp[i-1][0] * (1-prob[i-1])\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,target+1):\n",
    "                dp[i][j] = dp[i-1][j-1] * prob[i-1] + dp[i-1][j] * (1-prob[i-1])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        if target == 0:\n",
    "            return prod([1-p for p in prob])\n",
    "        n = len(prob)\n",
    "        dp = [[0 for _ in range(target+1)] for _ in range(n)]\n",
    "\n",
    "        dp[0][0] = 1 - prob[0]\n",
    "        dp[0][1] = prob[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(target+1):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] * (1 - prob[i])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j] * (1 - prob[i]) + dp[i-1][j-1] * prob[i]\n",
    "        \n",
    "        return dp[n-1][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        dp = [[0 for j in range(target+1)] for i in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n+1):\n",
    "            dp[i][0] = dp[i-1][0] * (1 - prob[i-1])\n",
    "            for j in range(1,target+1):\n",
    "                dp[i][j] = dp[i-1][j-1] * prob[i-1] + dp[i-1][j] * (1 - prob[i-1])\n",
    "        return dp[n][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        dp = [[0 for _ in range(target + 1)] for __ in range(n)]\n",
    "        dp[0][0] = 1- prob[0]\n",
    "        if target >= 1:\n",
    "            dp[0][1] = prob[0]\n",
    "        for i in range(1,n):\n",
    "            for j in range(target+1):\n",
    "                dp[i][j] = dp[i-1][j] * (1-prob[i]) + (\n",
    "                    dp[i-1][j-1] * prob[i] if j - 1>= 0 else 0\n",
    "                )\n",
    "        \n",
    "        return dp[n-1][target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n=len(prob)\n",
    "        dp=[[0 for _ in range(target+1)] for _ in range(n+1)]\n",
    "        dp[0][0]=1\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(target+1):\n",
    "                if j==0:\n",
    "                    dp[i][j]=dp[i-1][j]*(1-prob[i-1])\n",
    "                else:\n",
    "                    dp[i][j]=dp[i-1][j]*(1-prob[i-1])+dp[i-1][j-1]*(prob[i-1])\n",
    "        #print(dp)\n",
    "        return dp[-1][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        dp = [[0 for _ in range(target+1)] for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n+1):\n",
    "            dp[i][0] = dp[i-1][0]*(1-prob[i-1])\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, target+1):\n",
    "                dp[i][j] = dp[i-1][j-1]*prob[i-1] + dp[i-1][j]*(1-prob[i-1])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        dp = [[0 for _ in range(target+1)] for _ in range(n+1)]\n",
    "        if target == 0:\n",
    "            res = 1\n",
    "            for i in range(n):\n",
    "                res *= (1-prob[i])\n",
    "            return res\n",
    "        dp[0][0] = 1\n",
    "        for i in range(target+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[j][i] = dp[j-1][i-1]*prob[j-1] + dp[j-1][i]*(1-prob[j-1])\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n=len(prob)\n",
    "        dp=[[0 for i in range(n)]for j in range(target+1)]\n",
    "        for i in range(target+1):\n",
    "            for j in range(n):\n",
    "               \n",
    "                if i==0 and j!=0:\n",
    "                    dp[i][j]=dp[i][j-1]*(1-prob[j])\n",
    "                elif j==0:\n",
    "                    if i==0:\n",
    "                        dp[i][j]=(1-prob[j])\n",
    "                    elif i==1:\n",
    "                        dp[i][j]=prob[j]\n",
    "                    else:\n",
    "                        dp[i][j]=0\n",
    "                else:\n",
    "                    dp[i][j]=dp[i-1][j-1]*prob[j]+dp[i][j-1]*(1-prob[j])\n",
    "        # for i in dp:\n",
    "        #     print(i)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n=len(prob)\n",
    "        dp=[[0 for _ in range(n+1)]for _ in range(n)]\n",
    "        dp[0][0]=1-prob[0]\n",
    "        dp[0][1]=prob[0]\n",
    "        for i,p in enumerate(prob):\n",
    "            for j in range(target+1):\n",
    "                # 0情况要剔除\n",
    "                if i>0:\n",
    "                    dp[i][j]=dp[i-1][j]*(1-p)+dp[i-1][j-1]*(p)\n",
    "        return dp[-1][target]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n=len(prob)\n",
    "        dp=[[0 for _ in range(n+1)]for _ in range(n)]\n",
    "        dp[0][0]=1-prob[0]\n",
    "        dp[0][1]=prob[0]\n",
    "        for i,p in enumerate(prob):\n",
    "            for j in range(target+1):\n",
    "                if i>0:\n",
    "                    dp[i][j]=dp[i-1][j]*(1-p)+dp[i-1][j-1]*(p)\n",
    "        return dp[-1][target]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n+1):\n",
    "            dp[n][0] = dp[i-1][0] * (1-prob[i-1])\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(n+1):\n",
    "                dp[i][j] = dp[i-1][j]*(1-prob[i-1]) + dp[i-1][j-1]*prob[i-1]\n",
    "        return dp[n][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        if target>n:\n",
    "            return 0 \n",
    "        \n",
    "        dp = [[0] * (n+1) for _ in range(n)]\n",
    "        dp[0][0] = 1 - prob[0]\n",
    "        dp[0][1] = prob[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][0] * (1-prob[i])\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = dp[i-1][j-1] * prob[i] + dp[i-1][j] * (1-prob[i])\n",
    "        \n",
    "        return dp[-1][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        f = [[-1] * (target + 1) for _ in range(len(prob))]\n",
    "        def dfs(i, j):\n",
    "            if i == len(prob):\n",
    "                return 1.0 if j == 0 else 0.0\n",
    "            if j < 0:\n",
    "                return 0.0\n",
    "            if f[i][j] == -1:\n",
    "                f[i][j] = dfs(i + 1, j - 1) * prob[i] + dfs(i + 1, j) * (1 - prob[i])\n",
    "            return f[i][j]\n",
    "        return dfs(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "\n",
    "        cache={}\n",
    "\n",
    "        length =len(prob)\n",
    "        def dp_help(n,head):\n",
    "            if n ==length :\n",
    "                if  head==target:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if length-n <target-head:\n",
    "                return 0\n",
    "            \n",
    "\n",
    "            if (n,head) in cache:\n",
    "                return cache[(n,head)]\n",
    "            \n",
    "            if head==target:\n",
    "                cache[(n,head)] = dp_help(n+1, head)*(1-prob[n])\n",
    "            else:\n",
    "                cache[(n,head)]= dp_help(n+1, head+1)*prob[n]+\\\n",
    "                dp_help(n+1, head)*(1-prob[n])\n",
    "                \n",
    "            return cache[(n,head)]\n",
    "\n",
    "        return dp_help(0, 0)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "\n",
    "        cache={}\n",
    "\n",
    "        length =len(prob)\n",
    "        def dp_help(n,head):\n",
    "            if n ==length :\n",
    "                if  head==target:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if length-n <target-head:\n",
    "                return 0\n",
    "            \n",
    "\n",
    "            if (n,head) in cache:\n",
    "                return cache[(n,head)]\n",
    "            \n",
    "            if head==target:\n",
    "                cache[(n,head)] = dp_help(n+1, head)*(1-prob[n])\n",
    "            else:\n",
    "                cache[(n,head)]= dp_help(n+1, head+1)*prob[n]+\\\n",
    "                dp_help(n+1, head)*(1-prob[n])\n",
    "                \n",
    "            return cache[(n,head)]\n",
    "\n",
    "        return dp_help(0, 0)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        @lru_cache(None)\n",
    "        def dfs(left, target):\n",
    "            if n - left < target:\n",
    "                return 0\n",
    "            \n",
    "            if target == 0:\n",
    "                a = 1\n",
    "                for i in prob[left:]:\n",
    "                    a *= (1 - i)\n",
    "                return a\n",
    "            \n",
    "            return prob[left] * dfs(left + 1, target-1) + (1 - prob[left]) * dfs(left + 1, target)\n",
    "        \n",
    "        return dfs(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        @lru_cache(None)\n",
    "        def dfs(left, target):\n",
    "            if n - left < target:\n",
    "                return 0\n",
    "            \n",
    "            if target == 0:\n",
    "                a = 1\n",
    "                for i in prob[left:]:\n",
    "                    a *= (1 - i)\n",
    "                return a\n",
    "            \n",
    "            return prob[left] * dfs(left + 1, target-1) + (1 - prob[left]) * dfs(left + 1, target)\n",
    "        \n",
    "        return dfs(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "\n",
    "        n = len(prob)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,sumup):\n",
    "            if i<0:\n",
    "                return 0 if sumup!=target else 1\n",
    "            if sumup>target:\n",
    "                return 0\n",
    "            return prob[i]*dfs(i-1,sumup+1)+(1-prob[i])*dfs(i-1,sumup)\n",
    "        \n",
    "        return dfs(n-1,0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        res = {}\n",
    "\n",
    "        #@cache\n",
    "        def iter(index, target, n):\n",
    "            if target < 0:\n",
    "                return 0\n",
    "            if index == n:\n",
    "                if target == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if (index, target) in res:\n",
    "                return res[index, target]\n",
    "\n",
    "            res[index, target] = iter(index + 1, target - 1, n) * prob[index] + \\\n",
    "                                 iter(index + 1, target, n) * (1 - prob[index])\n",
    "            #print(res)\n",
    "            return res[index, target]\n",
    "            print(res)\n",
    "        return iter(0, target, len(prob))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        memo = {}\n",
    "\n",
    "        def findProbability(index, target, n):\n",
    "            # 如果 target 小于 0，则返回 0，因为我们有比需要的更多的正面\n",
    "            if target < 0:\n",
    "                return 0\n",
    "            # 扔完所有的硬币后，如果我们得到了所需的正面数，\n",
    "            # 返回 1 来计数这个情况，否则返回 0。\n",
    "            if index == n:\n",
    "                if target == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "\n",
    "            if (index, target) in memo:\n",
    "                return memo[index, target]\n",
    "\n",
    "            memo[index, target] = findProbability(index + 1, target - 1, n) * prob[index] + \\\n",
    "                                  findProbability(index + 1, target, n) * (1 - prob[index])\n",
    "\n",
    "            return memo[index, target]\n",
    "\n",
    "        return findProbability(0, target, len(prob))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        memo = {}\n",
    "\n",
    "        def findProbability(index, target, n):\n",
    "            # 如果 target 小于 0，则返回 0，因为我们有比需要的更多的正面\n",
    "            if target < 0:\n",
    "                return 0\n",
    "            # 扔完所有的硬币后，如果我们得到了所需的正面数，\n",
    "            # 返回 1 来计数这个情况，否则返回 0。\n",
    "            if index == n:\n",
    "                if target == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "\n",
    "            if (index, target) in memo:\n",
    "                return memo[index, target]\n",
    "\n",
    "            memo[index, target] = findProbability(index + 1, target - 1, n) * prob[index] + \\\n",
    "                                  findProbability(index + 1, target, n) * (1 - prob[index])\n",
    "\n",
    "            return memo[index, target]\n",
    "\n",
    "        return findProbability(0, target, len(prob))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        memo = {}\n",
    "\n",
    "        def findProbability(index, target, n):\n",
    "            # 如果 target 小于 0，则返回 0，因为我们有比需要的更多的正面\n",
    "            if target < 0:\n",
    "                return 0\n",
    "            # 扔完所有的硬币后，如果我们得到了所需的正面数，\n",
    "            # 返回 1 来计数这个情况，否则返回 0。\n",
    "            if index == n:\n",
    "                if target == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "\n",
    "            if (index, target) in memo:\n",
    "                return memo[index, target]\n",
    "\n",
    "            memo[index, target] = findProbability(index + 1, target - 1, n) * prob[index] + \\\n",
    "                                  findProbability(index + 1, target, n) * (1 - prob[index])\n",
    "\n",
    "            return memo[index, target]\n",
    "\n",
    "        return findProbability(0, target, len(prob))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "\n",
    "        cache={}\n",
    "\n",
    "        length =len(prob)\n",
    "        def dp_help(n,head):\n",
    "            if n ==length :\n",
    "                if  head==target:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            \n",
    "\n",
    "            if (n,head) in cache:\n",
    "                return cache[(n,head)]\n",
    "            \n",
    "            if head==target:\n",
    "                cache[(n,head)] = dp_help(n+1, head)*(1-prob[n])\n",
    "            else:\n",
    "                cache[(n,head)]= dp_help(n+1, head+1)*prob[n]+\\\n",
    "                dp_help(n+1, head)*(1-prob[n])\n",
    "                \n",
    "            return cache[(n,head)]\n",
    "\n",
    "        return dp_help(0, 0)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "\n",
    "        cache={}\n",
    "\n",
    "        length =len(prob)\n",
    "        def dp_help(n,head):\n",
    "            if n ==length :\n",
    "                if  head==target:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            \n",
    "\n",
    "            if (n,head) in cache:\n",
    "                return cache[(n,head)]\n",
    "            \n",
    "            if head==target:\n",
    "                cache[(n,head)] = dp_help(n+1, head)*(1-prob[n])\n",
    "            else:\n",
    "                cache[(n,head)]= dp_help(n+1, head+1)*prob[n]+\\\n",
    "                dp_help(n+1, head)*(1-prob[n])\n",
    "                \n",
    "            return cache[(n,head)]\n",
    "\n",
    "        return dp_help(0, 0)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        memo = {}\n",
    "\n",
    "        def findProbability(index, target, n):\n",
    "            # 如果 target 小于 0，则返回 0，因为我们有比需要的更多的正面\n",
    "            if target < 0:\n",
    "                return 0\n",
    "            # 扔完所有的硬币后，如果我们得到了所需的正面数，\n",
    "            # 返回 1 来计数这个情况，否则返回 0。\n",
    "            if index == n:\n",
    "                if target == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "\n",
    "            if (index, target) in memo:\n",
    "                return memo[index, target]\n",
    "\n",
    "            memo[index, target] = findProbability(index + 1, target - 1, n) * prob[index] + \\\n",
    "                                  findProbability(index + 1, target, n) * (1 - prob[index])\n",
    "\n",
    "            return memo[index, target]\n",
    "\n",
    "        return findProbability(0, target, len(prob))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        memo = {}\n",
    "        def findProbability(index, target,n):\n",
    "            if target < 0 :\n",
    "                return 0\n",
    "            if index == n :\n",
    "                if target == 0 :\n",
    "                    return 1 \n",
    "                else:\n",
    "                    return 0 \n",
    "            if (index,target) in memo:\n",
    "                return memo[(index,target)]\n",
    "\n",
    "            memo[(index,target)] = findProbability(index +1, target-1,n) * prob[index] + findProbability(index+1,target, n) * (1-prob[index])\n",
    "            return memo[(index,target)]\n",
    "        return findProbability(0, target,len(prob))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            if i == n:\n",
    "                return 1 if j == target else 0\n",
    "            res = 0\n",
    "            if j+1<=target:\n",
    "                res += dfs(i+1,j+1)*prob[i]\n",
    "            res += dfs(i+1, j)*(1-prob[i])\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        # f = [[-1] * (target + 1) for _ in range(len(prob))]\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == len(prob):\n",
    "                return 1.0 if j == 0 else 0.0\n",
    "            if j < 0:\n",
    "                return 0.0\n",
    "            # if f[i][j] == -1:\n",
    "            #     f[i][j] = dfs(i + 1, j - 1) * prob[i] + dfs(i + 1, j) * (1 - prob[i])\n",
    "            # return f[i][j]\n",
    "            return dfs(i + 1, j - 1) * prob[i] + dfs(i + 1, j) * (1 - prob[i])\n",
    "        return dfs(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(i, target):\n",
    "            if target < 0:\n",
    "                return 0\n",
    "            if i == n:\n",
    "                if target == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            p1 = dfs(i+1, target-1)*prob[i]\n",
    "            p2 = dfs(i+1, target)*(1-prob[i])\n",
    "            return p1 + p2\n",
    "\n",
    "        return dfs(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        @cache\n",
    "        def dfs(index, target, n):\n",
    "            if target < 0:\n",
    "                return 0\n",
    "            if index == n:\n",
    "                if target == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            return dfs(index + 1, target - 1, n) * prob[index] + dfs(index + 1, target, n) * (1 - prob[index])\n",
    "\n",
    "        return dfs(0, target, len(prob))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        @cache\n",
    "        def dfs(index, target, n):\n",
    "            if target < 0:\n",
    "                return 0\n",
    "            if index == n:\n",
    "                if target == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            return dfs(index + 1, target - 1, n) * prob[index] + dfs(index + 1, target, n) * (1 - prob[index])\n",
    "\n",
    "        return dfs(0, target, len(prob))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def probabilityOfHeads(self, prob: List[float], target: int) -> float:\n",
    "        n = len(prob)\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(i, target):\n",
    "            if target < 0:\n",
    "                return 0\n",
    "            if i == n:\n",
    "                if target == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            return dfs(i+1, target-1)*prob[i] + dfs(i+1, target)*(1-prob[i])\n",
    "\n",
    "        return dfs(0, target)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
